Remember Your Primes
Once I witnessed John H. Conway factoring large numbers in his head. Impressed, I stared at him. Encouraged by my interest, he told me that if I ever want to be able to factor large numbers, I should know all the primes below one thousand.
The secret to knowing all such primes is to remember the composites, he continued. Obviously, we don’t need to remember trivial composites — the ones divisible by 2, 3, 5, or 11. Also, everyone knows all the squares below one thousand, so we can count squares as trivial composites. We only need to remember the non-trivial composites. There are not that many of them below one thousand — only 70. I mean, 70 is nothing compared to the number of primes: 168.
So, I need to remember the following seventy numbers:
91, 119, 133, 161, 203, 217, 221, 247, 259, 287, 299, 301, 323, 329, 343, 371, 377, 391, 403, 413, 427, 437, 469, 481, 493, 497, 511, 527, 533, 551, 553, 559, 581, 589, 611, 623, 629, 637, 667, 679, 689, 697, 703, 707, 713, 721, 731, 749, 763, 767, 779, 791, 793, 799, 817, 833, 851, 871, 889, 893, 899, 901, 917, 923, 931, 943, 949, 959, 973, 989.
If you are very ambitious and plan to learn the primes up to 50,000, then the trick of learning non-trivial composites instead of primes is of no use to you. Indeed, for larger numbers the density of primes goes down, while the density of non-trivial composites stays about the same or increases very slightly due to a smaller number of squares.
The turning point is around 11,625: the number of primes below 11,625 equals the number of non-trivial composites below it. So, compare your ambition to 11,625 and tailor your path of learning accordingly.
If you are lazy, you can learn primes only up to 100. In this case your path is clear; you should stick with remembering non-trivial composites, for you need to remember only one number: 91.
Share:
Tanya Khovanova’s Math Blog » Blog Archive » Turning Numbers Inside Out:
[…] Here is how he beat me. If you have two not-too-big primes that consist of zeroes and ones and that are reversals of each other, their product will be a palindrome. And John is really fast in checking primes for primality. See his lesson in my essay Remember Your Primes. […]
24 June 2009, 4:23 pmRecognize your Primes « Konstantin’s Weblog:
[…] your Primes By zieglerk After reading Tanya Khovanova’s Remember your Primes, I decided to do so. The description is due to John […]
12 July 2009, 1:12 am